GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Ramanujan-Graph</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Ramanujan-Graph</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Im <a href="Mathematik" title="Mathematik">mathematischen</a> Gebiet der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> sind <b>Ramanujan-Graphen</b> Graphen mit besonderen Regularitäts- und Stabilitätseigenschaften, die deshalb in verschiedenen Gebieten der Informatik und Mathematik von Interesse sind.

</p><p>Der Graph ist nach <a href="S._Ramanujan" class="mw-redirect" title="S. Ramanujan">S. Ramanujan</a> benannt, wobei der Name von <a href="Alexander_Lubotzky" title="Alexander Lubotzky">Alexander Lubotzky</a>, <a href="Ralph_Phillips" title="Ralph Phillips">Ralph Phillips</a> und <a href="Peter_Sarnak" title="Peter Sarnak">Peter Sarnak</a> stammt, die 1988 Ramanujan-Graphen einführten (sie benutzten ein Resultat von Ramanujan).

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>Ein <a href="Zusammenhang_(Graphentheorie)" title="Zusammenhang (Graphentheorie)">zusammenhängender</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-<a href="Regul%C3%A4rer_Graph" title="Regulärer Graph">regulärer Graph</a> ist ein Ramanujan-Graph, wenn alle <a href="Eigenwert" class="mw-redirect" title="Eigenwert">Eigenwerte</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy"></span> der <a href="Adjazenzmatrix" title="Adjazenzmatrix">Adjazenzmatrix</a> entweder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda =\pm k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda =\pm k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/07eee0a5ee73be76d6dbbc2b0c4fba3c57151462.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.473ex; height:2.176ex;" alt="{\displaystyle \lambda =\pm k}" loading="lazy"></span> oder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mid \lambda \mid \leq 2{\sqrt {k-1}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mid \lambda \mid \leq 2{\sqrt {k-1}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fa612771b85aa56a44d99e97b6dd4ca469584f6a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.06ex; height:3.343ex;" alt="{\displaystyle \mid \lambda \mid \leq 2{\sqrt {k-1}}}" loading="lazy"></span> erfüllen.

</p><p>Äquivalent lassen sich Ramanujan-Graphen dadurch charakterisieren, dass das Analog der <a href="Riemann-Vermutung" class="mw-redirect" title="Riemann-Vermutung">Riemann-Vermutung</a> für die Iharasche Zetafunktion gilt: alle <a href="Polstelle" title="Polstelle">Polstellen</a> im Bereich <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq Re(s)\leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq Re(s)\leq 1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/df607c3f0598496f079f4702624c4e745a63ee04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.269ex; height:2.843ex;" alt="{\displaystyle 0\leq Re(s)\leq 1}" loading="lazy"></span> liegen auf der <a href="Gerade" title="Gerade">Geraden</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Re(s)={\frac {1}{2}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Re(s)={\frac {1}{2}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0eb89707a6e457f92d1426579326636891401baa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.844ex; height:5.176ex;" alt="{\displaystyle Re(s)={\frac {1}{2}}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Ramanujan-Graphen_als_optimale_Expander">Ramanujan-Graphen als optimale Expander</h2></div>

<p><a href="Expander-Graph" title="Expander-Graph">Expander-Graphen</a> sind Graphen mit sehr guten Stabilitätseigenschaften (d. h., sie lassen sich nicht durch Entfernen relativ weniger Kanten in mehrere Zusammenhangskomponenten zerlegen), die deshalb in Mathematik und Informatik von großem Interesse sind. Eine Möglichkeit, die Expansitivität eines <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-regulären Graphen zu messen, ist durch den zweitgrößten Eigenwert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6b668a1bd1e8ab9452ca975b7497546e7c1ba187.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle \lambda _{2}}" loading="lazy"></span> der Adjazenzmatrix. (Der größte Eigenwert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/571a423bece8f29bcd1b48572f18dd4f6213dce2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle \lambda _{1}}" loading="lazy"></span> ist für einen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-regulären Graphen immer <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{1}=k}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{1}=k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c8c372d9dc3158200fad9b3b107c7fe1b9d4039.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.719ex; height:2.509ex;" alt="{\displaystyle \lambda _{1}=k}" loading="lazy"></span>.)

</p><p>Für einen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-regulären Graphen mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Ecken gilt die <a href="Ungleichung" title="Ungleichung">Ungleichung</a>

</p>

<msub>

</mrow>

</msub>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{2}\geq 2{\sqrt {k-1}}-o(1).}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34fff28a333ff9aaf9d333f5a2edac0c933a44ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.407ex; height:3.343ex;" alt="{\displaystyle \lambda _{2}\geq 2{\sqrt {k-1}}-o(1).}" loading="lazy"></span></dd></dl>

<p>Andererseits gilt für Ramanujan-Graphen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{2}\leq 2{\sqrt {k-1}}}">

<msub>

</mrow>

</msub>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{2}\leq 2{\sqrt {k-1}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a5db1e8570b5f42906aa50d8eda6b1ad69db55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.82ex; height:3.176ex;" alt="{\displaystyle \lambda _{2}\leq 2{\sqrt {k-1}}}" loading="lazy"></span>, diese haben für große <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> also annähernd optimale Expander-Eigenschaft.

</p>

<div class="mw-heading mw-heading2"><h2 id="Konstruktionen">Konstruktionen</h2></div>

<p>Es gibt verschiedene Konstruktionen von Ramanujan-Graphen. Für <a href="Primzahl" title="Primzahl">Primzahlen</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> benutzten Lubotzky-Philips-Sarnak<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> die <a href="Ramanujan-Vermutung" title="Ramanujan-Vermutung">Ramanujan-Vermutung</a> um zu beweisen, dass gewisse Quotienten des p-adischen symmetrischen Raums <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7841fdefd8cbdae9afd10c15e3ecb5f27be6694e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.961ex; height:3.009ex;" alt="{\displaystyle PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})}" loading="lazy"></span> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span>-reguläre Ramanujan-Graphen sind. Marcus-Spielman-Srivastava<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> konstruieren <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-reguläre Ramanujan-Graphen für beliebige <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<p>Der <a href="Petersen-Graph" title="Petersen-Graph">Petersen-Graph</a> ist ein Ramanujan-Graph.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Alexander_Lubotzky" title="Alexander Lubotzky">Alexander Lubotzky</a>: <i>Discrete groups, expanding graphs and invariant measures.</i> With an appendix by Jonathan D. Rogawski. Progress in Mathematics, 125. Birkhäuser Verlag, Basel, 1994. ISBN 3-7643-5075-X</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Alexander Lubotzky, Ralph Phillips, Peter Sarnak: <i>Ramanujan graphs</i>. Combinatorica 8 (1988), no. 3, 261–277. <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF02126799">10.1007/BF02126799</a></span>.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Kapitel 7.3 in Lubotzky, op.cit.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><a href="Adam_Marcus" title="Adam Marcus">Adam Marcus</a>, <a href="Daniel_Spielman" title="Daniel Spielman">Daniel Spielman</a>, <a href="Nikhil_Srivastava" title="Nikhil Srivastava">Nikhil Srivastava</a>: <i>Interlacing families I: Bipartite Ramanujan graphs of all degrees</i>. Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. <a rel="nofollow" class="external text" href="https://arxiv.org/pdf/1304.4132v2.pdf">online</a> (PDF; 196 kB).</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-12-06" href="https://de.wikipedia.org/wiki/?title=Ramanujan-Graph&oldid=251023701">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>